package www.study.com;

//解数独 https://leetcode.cn/problems/sudoku-solver/
public class code37 {
    public static void main(String[] args) {

    }

    class Solution {
        //解法二：优化存储
        public void solveSudoku(char[][] board) {
            int[] row = new int[9]; //row[i][n]：若 n & (1<<num) 为1，表示num被使用了
            int[] col = new int[9];
            int[] area = new int[9];
            initArr(row,col,area,board);
            dfs(row,col,area,board,0,0);
        }
        public boolean dfs(int[] row,int[] col,int[] area,char[][] board,int i,int j){
            if(i == 8 && j == 8){
                if(board[i][j] == '.'){
                    for(int num = 1 ; num <= 9 ; num++){
                        if(numInArr(row[i],num) || numInArr(col[j],num) || numInArr(area[findArea(i,j)],num)) continue;
                        board[i][j] = (char)(num + '0');
                        break;
                    }
                }
                return true;
            }
            int i2 = (j == board[0].length - 1 ? i + 1 : i);
            int j2 = (j == board[0].length - 1 ? 0 : j + 1);
            if(board[i][j] != '.') return dfs(row,col,area,board,i2,j2);
            for(int num = 1 ; num <= 9 ; num++){
                if(numInArr(row[i],num) || numInArr(col[j],num) || numInArr(area[findArea(i,j)],num)) continue;
                row[i] |= (1 << num);
                col[j] |= (1 << num);
                area[findArea(i,j)] |= (1 << num);
                board[i][j] = (char)(num + '0'); //记得＋'0'转义
                if(dfs(row,col,area,board,i2,j2)) return true;
                board[i][j] = '.';
                row[i] &= ~(1 << num);
                col[j] &= ~(1 << num);
                area[findArea(i,j)] &= ~(1 << num);
            }
            return false;
        }
        //判断数字n是否存储num
        public boolean numInArr(int n,int num){
            if((n & (1 << num)) != 0) return true; //在
            return false; //不在
        }
        public void initArr(int[] row,int[] col,int[] area,char[][] board){
            for(int i = 0 ; i < board.length ; i++){
                for(int j = 0 ; j < board[0].length ; j++){
                    if(board[i][j] == '.') continue;
                    int num = board[i][j] - '0'; //数字 1~9
                    row[i] |= (1 << num);
                    col[j] |= (1 << num);
                    area[findArea(i,j)] |= (1 << num);
                }
            }
        }
        //解法一：
    /*
    public void solveSudoku(char[][] board) {
        boolean[][] row = new boolean[9][10]; //row[i][num] - ture：表示i行数字num已经存在
        boolean[][] col = new boolean[9][10];
        boolean[][] area = new boolean[9][10]; //area[i][num] - true：表示区域i数字num已经存在
        initArr(row,col,area,board);
        dfs(row,col,area,board,0,0);
    }
    //flag为true，表示可以结束
    public boolean dfs(boolean[][] row,boolean[][] col,boolean[][] area,char[][] board,int i,int j){
        if(i == 8 && j == 8){
            if(board[i][j] == '.'){
                for(int num = 1 ; num <= 9 ; num++){
                    if(!row[i][num]) {
                        board[i][j] = (char)(num + '0');
                        break;
                    }
                }
            }
            //System.out.println("win");
            return true;
        }
        int i2 = (j == (board[0].length - 1)) ? i + 1 : i;
        int j2 = (j == (board[0].length - 1)) ? 0 : j + 1;
        if(board[i][j] != '.') return dfs(row,col,area,board,i2,j2); //注意这里，如果当前位置有数字，需要直接移动到下一个位置
        for(int num = 1 ; num <= 9 ; num++){
            if(!row[i][num] && !col[j][num] && !area[findArea(i,j)][num]){
                row[i][num] = true;
                col[j][num] = true;
                area[findArea(i,j)][num] = true;
                board[i][j] = (char)(num + '0');
                if (dfs(row,col,area,board,i2,j2)) return true;
                board[i][j] = '.';
                row[i][num] = false;
                col[j][num] = false;
                area[findArea(i,j)][num] = false;
            }
        }
        return false;
    }
    public void initArr(boolean[][] row,boolean[][] col,boolean[][] area,char[][] board){
        for(int i = 0 ; i < board.length ; i++){
            for(int j = 0 ; j < board[0].length ; j++){
                if(board[i][j] == '.') continue;
                int num = board[i][j] - '0';
                row[i][num] = true;
                col[j][num] = true;
                area[findArea(i,j)][num] = true;
            }
        }
    }
    */
        public int findArea(int i,int j){
            return i / 3 * 3 + j / 3;
        }
    }
}
